package mo.tags.greedy;

import java.util.Deque;
import java.util.LinkedList;

public class L402 {

    public String removeKdigits(String num, int k) {
        Deque<Character> deque = new LinkedList<>();
        for (int i = 0; i < num.length(); i++) {
            char c = num.charAt(i);
            while (!deque.isEmpty() && k > 0 && deque.peekLast() > c) {
                deque.pollLast();
                k--;
            }
            deque.add(c);
        }

        while (k > 0) {
            deque.pollLast();
            k--;
        }

        StringBuilder res = new StringBuilder();
        boolean flag = true;
        while (!deque.isEmpty()) {
            char c = deque.pollFirst();
            if (flag && c == '0') {
                continue;
            }
            flag = false;
            res.append(c);
        }

        return res.length() == 0 ? "0" : res.toString();
    }

}
